package linkedList.双指针;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 面试题回文链表0206.java
 * @Description https://leetcode.cn/problems/palindrome-linked-list/
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
 * @createTime 2021年03月24日 12:58:00
 */
public class 面试题回文链表0206 extends BaseLinkedListTest {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fastNode = head, slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        ListNode temp = slowNode;
        if (fastNode != null) {
            temp = slowNode.next;
        }
        ListNode node = reverseNode(temp);
        ListNode p1 = head, p2 = node;
        boolean result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return result;
    }

    private ListNode reverseNode(ListNode temp) {
        if (temp == null || temp.next == null) {
            return temp;
        }
        ListNode node = reverseNode(temp.next);
        temp.next.next = temp;
        temp.next = null;
        return node;
    }
}
